<?php
/**
 * ExpressionParser
 * 
 * This class parses an expression and converts it into
 * an abstract syntax tree.
 * 
 * Expression must adhere to the Junction Expression Grammar
 * defined below.
 * 
 * Each nonterminal (i.e, O, A, N, etc...) represents a levevel of precedence.
 * 
 * {}* indicates that the enclosed can repeat n times (0 <= n < infinity).
 * [] indicates that the enclosed is optional.
 * v is a variable.
 * 
 * O := A { "||" A } *
 * A := N { "&&" N } *
 * N := [ "!" ] C
 * C := P { ( "==" | "!=" | "<" | ">" | "<=" | ">=" ) P } *
 * P := v | "'" v "'" | "(" O ")"
 * 
 * @author Patrick J. Mizer <patrick.mizer@gmail.com>
 */
 
class ExpressionParser extends GrammarParser
{		
	/**
	 * Parses the expression.
	 * 
	 * @throws Exception Malformed expression.
	 * @return AbstractSyntaxTree representation of expression.
	 */
	public function parse()
	{
		$tree = $this->_parseO();

		$this->_expect(GrammarParser::END_CHAR);
		
		return new AbstractSyntaxTree($tree);
	}
	
	/**
	 * Parses the nonterminal P
	 * 
	 * @return BinaryTreeNode
	 */
	private function _parseP()
	{
   		if($this->_isV($this->_next())){
   			$tree = $this->_createLeaf($this->_next());
   			$this->_consume();
   			return $tree;
   		}else if($this->_next() == '('){
   			$this->_consume();
   			$tree = $this->_parseO();
   			$this->_expect(')');
   			return $tree;
   		}else {
   			throw new Exception('Parse Error!');
   		}
	}
	
	/**
	 * Parses the nonterminal C
	 */	
	private function _parseC()
	{
		$tree = $this->_parseP();
		
		while(in_array($this->_next(), array("==", "!=", "<", ">", "<=", ">="))){
			$op = $this->_next();
			$this->_consume();
			$subTree = $this->_parseP();
			$tree = $this->_createNode($op, $tree, $subTree);
		}
		return $tree;
	}
	
	/**
	 * Parses the nonterminal N
	 */	
	private function _parseN()
	{
		if($this->_next() == '!'){
			$op = $this->_next();
			$this->_consume();
			$tree = $this->_parseC();
			return $this->_createNode($op, $tree, null);
		}else 
			return $this->_parseC();
	}	
	
	/**
	 * Parses the nonterminal A
	 */	
	private function _parseA()
	{
		$tree = $this->_parseN();
		
		while($this->_next() == "&&"){
			$op = $this->_next();
			$this->_consume();
			$subTree = $this->_parseN();
			$tree = $this->_createNode($op, $tree, $subTree);
		}		
		
		return $tree;
	}
	
	/**
	 * Parses the nonterminal O
	 */	
	private function _parseO()
	{
		$tree = $this->_parseA();
		
		while($this->_next() == "||"){
			$op = $this->_next();
			$this->_consume();
			$subTree = $this->_parseN();
			$tree = $this->_createNode($op, $tree, $subTree);
		}		
		
		return $tree;		
	}
	
	private function _createLeaf($var)
	{
		return new BinaryTreeNode($var);
	}
	
	private function _createNode($op, BinaryTreeNode $left = null, BinaryTreeNode $right = null)
	{
		$node = new BinaryTreeNode($op);
		$node->setLeft($left);
		$node->setRight($right);
		
		return $node;
	}
	
	protected function _getBinaryOperators()
	{
	 	return array(
			'&&', 
			'||', 
			'==', 
			'!=',
			'<',
			'>',
			'<=',
			'>='
	 	);
	}	
	
	protected function _getUnaryOperators()
	{
		return array(
			'!'	 			
		);
	}
	
	protected function _getGroupingTokens()
	{
		return array(
			'(', 
			')', 
			"'"
	 	);	 		
	}
}
?>